#include <bits/stdc++.h>
using namespace std;

/*
1233. 删除子文件夹
已解答
中等
相关标签
premium lock icon
相关企业
提示
你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。folder[j] 的子文件夹必须以 folder[j] 开头，后跟一个 "/"。例如，"/a/b" 是 "/a" 的一个子文件夹，但 "/b" 不是 "/a/b/c" 的一个子文件夹。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符串和 "/" 不是。
 

示例 1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。
示例 2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d" 都会被删除，因为它们都是 "/a" 的子文件夹。
示例 3：

输入: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出: ["/a/b/c","/a/b/ca","/a/b/d"]
 

提示：

1 <= folder.length <= 4 * 104
2 <= folder[i].length <= 100
folder[i] 只包含小写字母和 '/'
folder[i] 总是以字符 '/' 起始
folder 每个元素都是 唯一 的
*/

// 法一
class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        // 排序文件名 字典序  父文件在子文件前面
        sort(folder.begin(), folder.end());

        // 存储向量容器 文件夹下的元素
        vector<string> ans;
        for (const string& s : folder) {
            if (ans.empty())
                ans.push_back(s);
            else {
                // 最后一个文件夹
                const auto& last = ans.back();
                // 对当前文件夹做检查
                // 1 子文件夹的路径长度肯定 > last 长度
                // 2 当前路径 last.size() + 1 == last + / 对应的长度
                if (s.size() > last.size() &&
                    s.substr(0, last.size() + 1) == last + "/") {
                    continue; // 是子文件夹就跳过
                } else
                    ans.push_back(s);
            }
        }

        return ans;
    }
};

// 法二
class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        // hash 前缀优化
        using HashType = unsigned long long;    // 无符号长整形防止溢出
        const int HASHBASE = 911;       // 大质数 减少冲突 提高性能

        // 排序重载 根据路径长度来升序
        sort(folder.begin(), folder.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });

        // 有效文件进哈希 常数量级 判断更快
        unordered_set<HashType> parentHash;
        vector<string> ans;

        for (const auto& path : folder) {
            // 每一个路径都有一个对应的哈希值
            HashType curHash = path[0];
            bool flag = true;       // 有效状态量
            // 遍历所有  看一看当前前缀哈希在没在父文件夹
            for (int i = 1; i < path.size(); i++) {
                // 累加当前位置的哈希  hash = hash * base + curstr
                curHash = curHash * HASHBASE + path[i];
                // 当前位置是不是路径中的文件夹分割点
                // condition 1 i是最后一个字符 
                // condition 2 下一个字符是"/"
                if (i == path.size() - 1 || path[i + 1] == '/') {
                    // 该前缀哈希存在 就是子文件夹
                    if (parentHash.count(curHash)) {
                        flag = false;
                        break;      // 这里确定是子文件夹了 不需要检查了
                    }
                }
            }
            // 有效父文件夹的情况 就加入结果集 记录哈希
            if (flag) {
                parentHash.insert(curHash);
                ans.push_back(path);
            }
        }
        return ans;
    }
};